Slide 12: BST Maintenance: Deletion & Balancing

BST Deletion: Preserving the Invariant

Removing a node from a BST must maintain the ordering invariant. The complexity of deletion depends on the node's children count:

Case 1: Node is a Leaf (0 Children): Simply remove the node and update the parent pointer to `NULL`.
Case 2: Node has 1 Child: Replace the node with its sole child. The child takes the node's position and inherits its parent.
Case 3: Node has 2 Children (The Complex Case): The node must be replaced by either its In-Order Successor (the smallest key in the right subtree) or its In-Order Predecessor (the largest key in the left subtree). Replacing the node with the successor (S) ensures the BST property holds, and S is guaranteed to have at most one child (simplifying the recursive deletion of S).

Preventing Skew: The Need for Balancing

Repeated insertions/deletions can lead to a skewed (degenerate) tree structure, where the BST acts like a linked list, degrading efficiency from $O(\log N)$ to $O(N)$. Self-balancing trees (like AVL Trees) address this using Balance Factors (BF) and Rotations.

Operation	Unbalanced BST (Worst Case)	Balanced BST (AVL/Red-Black)
Search	$O(H) \implies O(N)$	$O(\log N)$
Insertion	$O(H) \implies O(N)$	$O(\log N)$
Deletion	$O(H) \implies O(N)$	$O(\log N)$

The Balance Factor is calculated as: $BF = \text{Height}(L_{subtree}) - \text{Height}(R_{subtree})$. An AVL tree requires $|BF| \le 1$ for every node.

Rotation Mechanics: Restoring Balance

Rotations are local structural adjustments that restore the balance factor constraint while preserving the overall BST property.

⚙️ Quick Guide: Single Rotation (RR Example)

Rotations essentially pivot the structure around a specific node to move deeper nodes closer to the root, shortening the overall height.

Identify the Pivot (Z): The first node encountered (starting from the newly inserted/deleted node) where $|BF| > 1$.
Identify the Child (Y) and Grandchild (X): Determine the path causing the imbalance (e.g., Left-Left, Right-Right).
Perform Rotation: A single rotation (e.g., Left Rotation for an RR violation) moves the child (Y) up into the pivot's (Z) position, transferring subtrees to maintain the ordering.

Goal: Ensure the height of the tree $H$ remains proportional to $\log N$.

📝 Interactive Quiz

1. When deleting a node with two children, which node is a valid replacement to maintain the BST property?

A) The parent of the node.
B) The largest key in the right subtree.
C) The smallest key in the right subtree (In-Order Successor).
D) Any leaf node in the tree.

2. What is the primary consequence of a BST becoming skewed or degenerate?

A) It uses significantly more memory.
B) Its search/insert/delete performance degrades to $O(N)$.
C) It can no longer store duplicate values.
D) In-order traversal no longer produces a sorted list.

3. In a self-balancing tree like an AVL tree, what is the maximum allowed absolute value for the Balance Factor ($|BF|$) of any node?

A) 0
B) 1
C) 2
D) $N$

4. What is the main purpose of performing a rotation in a self-balancing BST?

A) To delete a node from the tree.
B) To sort the elements in the tree.
C) To restore the balance factor constraint while preserving the BST property.
D) To find the in-order successor of a node.

KEY TIPS

💡 Key Tips

Deletion is Tricky

The two-child deletion case is the most error-prone part of implementing a BST. Pay close attention to pointer updates.

Successor vs. Predecessor

You can use either the in-order successor or predecessor to replace a node with two children. Be consistent in your implementation.

Rotations are Local

A rotation is a constant time $O(1)$ operation that only rearranges pointers between a few nodes, but it has a global effect on the tree's balance.

Recursive Deletion

After replacing a node's value with its successor's, you must then delete the successor node. This recursive call is simpler, as the successor has at most one child.